The present disclosure relates in general to highly connected subgraphs. More specifically, the present disclosure relates to systems and methodologies for constructing an efficient heuristic algorithm to find a high-quality approximate solution for the densest subgraph problem.
In mathematics and computer science, graph theory is the study of graphs that are mathematical structures used to model so-called “pair-wise” relationships between objects. In its broadest sense, a graph is made up of a set of objects and lines that connect the objects. The objects are often referred to as “nodes” or “vertices,” and the lines connecting them are often referred to as “edges.” A graph may be undirected, which means that there is no distinction between the two vertices associated with each edge. A graph may also be directed, which means that edges connecting two vertices are directed from one vertex to another. FIG. 1 depicts a diagram illustrating a simplified example of a directed graph having 10 vertices and 13 edges. Graphs can be used to model many types of relations and processes in physical, biological, social and information systems.
A directed graph may be defined as an ordered pair G=(V, E), wherein V represents a set of V vertices, and E represents a set E of edges. In other words, an edge is related with two vertices, and the relation is represented as an unordered pair of vertices with respect to the particular edge. A subgraph of a graph includes a vertex set that is a subset of the vertex set of the graph, as well as an adjacency relation that is a subset of the adjacency relation of the graph.
FIG. 2 depicts a diagram illustrating a simplified example of the so-called densest subgraph problem, wherein given a graph G, a dense subgraph S of graph G must be located. In almost any network, density is an indication of importance. Depending on what properties are being modeled by the graph's vertices and edges, dense regions may indicate high degrees of interaction, mutual similarity, collective characteristics, attractive forces, favorable environments, or critical mass. Thus, a solution to the densest subgraph problem has many applications including social network analysis, biology, physics, information systems, and the like.